//
// Description: 5845. 你能穿过矩阵的最后一天
// Created by Loading on 2021/8/15.
//

#include <bits/stdc++.h>

using namespace std;

/* 二分查找 + DFS */
// 定义全局变量
vector<vector<int>> cells_;
int row_, col_;

bool check(int mid) {
    // 淹没后的数组
    vector<vector<int>> v(row_, vector<int>(col_));
    // 访问数组
    vector<vector<int>> visit(row_, vector<int>(col_));

    // DFS 方法
    function<bool(int, int)> dfs = [&](int i, int j) {
        // 能够到达最后一行
        if (i == row_ - 1) {
            return true;
        }
        // 访问状态置为 1
        visit[i][j] = 1;
        // 四个方向继续寻找
        // 左
        if (j - 1 >= 0 && v[i][j - 1] == 0 && visit[i][j - 1] == 0) {
            if (dfs(i, j - 1)) {
                return true;
            }
        }
        // 右
        if (j + 1 < col_ && v[i][j + 1] == 0 && visit[i][j + 1] == 0) {
            if (dfs(i, j + 1)) {
                return true;
            }
        }
        //上
        if (i - 1 >= 0 && v[i - 1][j] == 0 && visit[i - 1][j] == 0) {
            if (dfs(i - 1, j)) {
                return true;
            }
        }
        // 下
        if (i + 1 < row_ && v[i + 1][j] == 0 && visit[i + 1][j] == 0) {
            if (dfs(i + 1, j)) {
                return true;
            }
        }

        return false;
    };

    // 构造淹没后的数组
    for (int i = 0; i < mid; ++i) {
        v[cells_[i][0] - 1][cells_[i][1] - 1] = 1;
    }
    // 查找路径
    for (int i = 0; i < col_; ++i) {
        // 从第一行的每一位开始往下走
        if (v[0][i] == 0 && dfs(0, i)) {
            return true;
        }
    }
    return false;
}

int latestDayToCross(int row, int col, vector<vector<int>> &cells) {
    cells_ = cells;
    row_ = row;
    col_ = col;
    int n = row * col;
    int l = 0, r = n - 1;
    // 二分查找寻找最后一天
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int main() {
    vector<vector<int>> cells = {{1, 1},
                                 {2, 1},
                                 {1, 2},
                                 {2, 2}};
    int row = 2, col = 2;
    int res = latestDayToCross(row, col, cells);
    cout << res << endl;
}